/*
 * Essential-C - Essential C Libraries for Developers
 * Copyright (c) 2004-2008 Tom Bradford <tom@tbradford.org>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a 
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 * DEALINGS IN THE SOFTWARE.
 */

#include <stdlib.h>
#include <string.h>

#include "esc_list.h"

/* Private Types and Variables ***********************************************/

typedef struct esc_list_node_t esc_list_node_t;
typedef struct esc_list_location_t esc_list_location_t;

/** Implementation type for List instances */
struct esc_list_t {
    esc_list_node_t* head;
    esc_list_node_t* tail;
    int clusterSize;
    int listSize;
};

/** Implementation type for List entries */
struct esc_list_node_t {
    int entryCount;
    esc_list_node_t* prev;
    esc_list_node_t* next;
    void** entries;
};

/** Implementation type for List locators */
struct esc_list_location_t {
    esc_list_node_t* node;
    int entryIndex;
};

/* Private Functions *********************************************************/

static esc_list_node_t* private_createListNode(esc_list_t* list, 
                                               bool allocateEntries)
{
    esc_mem_t* mem = esc_ptr_getMem(list);
     
    esc_list_node_t* node = esc_mem_malloc(mem, sizeof(esc_list_node_t));

    node->entryCount = 0;
    node->prev = NULL;
    node->next = NULL;
    
    if ( allocateEntries )
        node->entries = esc_mem_calloc(mem, list->clusterSize, sizeof(void*));
    else
        node->entries = NULL;

    return node;
}

/*---------------------------------------------------------------------------*/

static void private_prepareForCopy(esc_list_t* list, esc_list_node_t* node)
{
    void** entries = node->entries;
    
    if ( !entries ) {
        esc_mem_t* mem = esc_ptr_getMem(list);        
        
        node->entries = esc_mem_calloc(mem, list->clusterSize, sizeof(void*));
    }
}

/*---------------------------------------------------------------------------*/

static esc_list_node_t* private_getListHead(esc_list_t* list)
{
    esc_list_node_t* head = list->head;
    
    if ( !head ) {
        head = private_createListNode(list, false);
        list->head = head;
        list->tail = head;
    }
    
    return head;
}

/*---------------------------------------------------------------------------*/

static esc_list_node_t* private_getListTail(esc_list_t* list)
{
    esc_list_node_t* tail = list->tail;
    
    if ( !tail ) {
        tail = private_createListNode(list, false);
        list->head = tail;
        list->tail = tail;
    }
    
    return tail;
}

/*---------------------------------------------------------------------------*/

static bool private_findListIndex(esc_list_t* list, int index, 
                                  esc_list_location_t* location, 
                                  bool insertion)
{
    int entryIndex = index;
    esc_list_node_t* node = list->head;
    
    while ( node ) {
        if ( insertion && (entryIndex == node->entryCount) 
             && (node->entryCount < list->clusterSize) ) {
                
            location->node = node;
            location->entryIndex = entryIndex + 1;
            
            return true;
        }        
        else if ( entryIndex < node->entryCount ) {
            location->node = node;
            location->entryIndex = entryIndex;
            
            return true;
        }
        else {
            entryIndex -= node->entryCount;
            node = node->next;
        }
    }
    
    return false;
}

/*---------------------------------------------------------------------------*/

static int private_findListItem(esc_list_t* list, void* item, 
                                esc_list_location_t* location)
{
    int index = 0;
    esc_list_node_t* node = list->head;
    
    while ( node ) {
        void** entries = node->entries;
        int entryCount = node->entryCount;
        
        for ( int i = 0; i < entryCount; i++, index++ ) {
            if ( entries[i] == item ) {
                location->node = node;
                location->entryIndex = i;
                
                return index;
            }
        }
        
        node = node->next;
    }
    
    return -1;
}

/*---------------------------------------------------------------------------*/

static void private_insertIntoSubrange(void** entries, int start, int end, 
                                       int index, void* item)
{
    int left = index - start;
    int right = (end - index) + 1;

    // Split and move entries on this node
    if ( left > 0 ) 
        memmove(entries, entries + start, left * sizeof(void*));
    
    if ( right > 0 ) {
        memmove(entries + (index - left), entries + index, 
                right * sizeof(void*));
    }

    entries[index - start] = item;
}

/*---------------------------------------------------------------------------*/

static void private_insertListItem(esc_list_t* list, 
                                   esc_list_location_t* location, void* item)
{
    esc_list_node_t* node = location->node;
    int entryIndex = location->entryIndex;

    if ( node->entryCount >= list->clusterSize ) {
        esc_list_node_t* prev = node->prev;
        esc_list_node_t* next = node->next;

        if ( prev && prev->entryCount < list->clusterSize ) {
            // Move entries to previous node
            int availEntries = list->clusterSize - prev->entryCount;
            
            if ( availEntries > entryIndex )
                availEntries = entryIndex;

            private_prepareForCopy(list, prev);

            memmove(prev->entries + prev->entryCount, node->entries, 
                    availEntries * sizeof(void*));
                    
            prev->entryCount += availEntries;

            private_insertIntoSubrange(node->entries, availEntries, 
                                       node->entryCount, entryIndex, item);
                                       
            node->entryCount = (node->entryCount - availEntries) + 1;
        }
        else if ( next && next->entryCount < list->clusterSize ) {
            // Move entries to next node
            int availEntries = list->clusterSize - next->entryCount;
            
            if ( availEntries > (node->entryCount - entryIndex) )
                availEntries = (node->entryCount - entryIndex);

            private_prepareForCopy(list, next);

            memmove(next->entries + availEntries, next->entries, 
                    next->entryCount * sizeof(void*));
                    
            memmove(next->entries, 
                    node->entries + (node->entryCount - availEntries), 
                    availEntries * sizeof(void*));
                    
            next->entryCount += availEntries;

            private_insertIntoSubrange(node->entries, 0, 
                                       node->entryCount - availEntries, 
                                       entryIndex, item);
                                       
            node->entryCount = (node->entryCount - availEntries) + 1;
        }
        else {
            // Split the current node
            int leftCount = node->entryCount / 2;
            int rightCount = node->entryCount - leftCount;

            int start, end, count;

            esc_list_node_t* newNode = private_createListNode(list, true);

            if ( entryIndex <= leftCount ) {
                memmove(newNode->entries, node->entries + leftCount, 
                        rightCount * sizeof(void*));
                        
                newNode->entryCount = rightCount;
                start = 0;
                end = leftCount - 1;
                count = leftCount;
                newNode->next = node->next;
                newNode->prev = node;
                
                if ( node->next )
                    node->next->prev = newNode;
                    
                node->next = newNode;
                
                if ( list->tail == node )
                    list->tail = newNode;
            }
            else {
                memmove(newNode->entries, node->entries, 
                        leftCount * sizeof(void*));
                        
                newNode->entryCount = leftCount;
                start = leftCount;
                end = (leftCount + rightCount) - 1;
                count = rightCount;
                newNode->prev = node->prev;
                newNode->next = node;
                
                if ( node->prev )
                    node->prev->next = newNode;
                                        
                node->prev = newNode;
                
                if ( list->head == node )
                    list->head = newNode;
            }

            private_insertIntoSubrange(node->entries, start, end, 
                                       entryIndex, item);
                                       
            node->entryCount = count + 1;
        }
    }
    else {
        private_prepareForCopy(list, node);

        if ( entryIndex < node->entryCount ) {
            memmove(node->entries + entryIndex + 1, node->entries + entryIndex, 
                    (node->entryCount - entryIndex) * sizeof(void*));
        }
        
        node->entries[entryIndex] = item;
        node->entryCount++;
    }
    
    list->listSize++;
}

/*---------------------------------------------------------------------------*/

static void private_removeListItem(esc_list_t* list, 
                                   esc_list_location_t* location)
{
    /*
     * The logic here is not perfect, nor is it meant to be.  Excessive
     * analysis of the list will detract from performance, and no analysis
     * will bloat the structure, also detracting from performance.  The 
     * key is to try to find a happy medium.
     */
    esc_list_node_t* node = location->node;
    int entryIndex = location->entryIndex;
    
    // Release the pointer
    esc_ptr_release(node->entries[entryIndex]);    
    
    if ( entryIndex < node->entryCount ) {
        memmove(node->entries + entryIndex, node->entries + entryIndex + 1, 
                ((node->entryCount - entryIndex) - 1) * sizeof(void*));
    }
    
    node->entryCount--;
    
    if ( node->entryCount > 0 ) {
        esc_list_node_t* prev = node->prev;
        esc_list_node_t* next = node->next;

        // If there's enough adjacent space, shift all data out of this Node
        int adjacentLeft = 0;
        int adjacentRight = 0;
        
        if ( prev )
            adjacentLeft = list->clusterSize - prev->entryCount;
            
        if ( next )
            adjacentRight = list->clusterSize - next->entryCount;

        if ( node->entryCount <= (adjacentLeft + adjacentRight) ) {
            if ( node->entryCount < adjacentLeft )
                adjacentLeft = node->entryCount;
                
            node->entryCount -= adjacentLeft;
            
            if ( node->entryCount < adjacentRight )
                adjacentRight = node->entryCount;
                
            node->entryCount -= adjacentRight;

            if ( adjacentLeft > 0 ) {
                memmove(prev->entries + prev->entryCount, node->entries, 
                        adjacentLeft * sizeof(void*));
                        
                prev->entryCount += adjacentLeft;
            }

            if ( adjacentRight > 0 ) {
                memmove(next->entries + adjacentRight, next->entries, 
                        next->entryCount * sizeof(void*));
                        
                memmove(next->entries, node->entries + adjacentLeft, 
                        adjacentRight * sizeof(void*));
                        
                next->entryCount += adjacentRight;
            }
            
            // Determine the new node and entryIndex for iterators
            if ( entryIndex < adjacentLeft ) {
                location->node = prev;
                location->entryIndex = prev->entryCount + entryIndex;
            }
            else {
                location->node = next;
                location->entryIndex = entryIndex - adjacentLeft;
            }
        }
    }
    else {
        location->node = node->next;
        location->entryIndex = 0;
    }

    // If the Node is empty, unlink it
    if ( node->entryCount == 0 ) {
        node->entries = NULL;

        // Relink Head and Tail Nodes
        if ( list->head == node )
            list->head = node->next;
            
        if ( list->tail == node )
            list->tail = node->prev;

        // Relink Previous and Next Nodes
        if ( node->prev )
            node->prev->next = node->next;
            
        if ( node->next )
            node->next->prev = node->prev;
            
        esc_ptr_free(node);
    }

    list->listSize--;
}

/* Public Functions **********************************************************/

esc_list_t* esc_list_new(esc_mem_t* mem)
{
    esc_list_t* list = esc_mem_malloc(mem, sizeof(esc_list_t));

    list->head = NULL;
    list->tail = NULL;
    list->clusterSize = 256;
    list->listSize = 0;

    esc_ptr_setDisposalFunction(list, esc_list_removeAll);

    return list;
}

/*---------------------------------------------------------------------------*/

void esc_list_setClusterSize(esc_list_t* list, int clusterSize)
{
    list->clusterSize = clusterSize;
}

/*---------------------------------------------------------------------------*/

int esc_list_getClusterSize(esc_list_t* list)
{
    return list->clusterSize;
}

/*---------------------------------------------------------------------------*/

void esc_list_addItem(esc_list_t* list, void* item)
{
    if ( !item )
        return;
      
    esc_list_node_t* tail = private_getListTail(list);
    
    if ( tail->entryCount >= list->clusterSize ) {
        esc_list_node_t* newTail = private_createListNode(list, true);
        tail->next = newTail;
        newTail->prev = tail;
        list->tail = newTail;
        tail = newTail;
    }
    else
        private_prepareForCopy(list, tail);

    esc_ptr_retain(item);
    tail->entries[tail->entryCount++] = item;
    
    list->listSize++;
}

/*---------------------------------------------------------------------------*/

void esc_list_insertItem(esc_list_t* list, int index, void* item)
{
    if ( !item )
        return;
        
    if ( index >= list->listSize ) {
        esc_list_addItem(list, item);
        
        return;
    }

    esc_list_node_t* head = private_getListHead(list);
    esc_list_location_t location; 
       
    if ( index <= 0 ) {
        location.node = head;
        location.entryIndex = 0;
    }
    else
        private_findListIndex(list, index, &location, true);

    esc_ptr_retain(item);
    private_insertListItem(list, &location, item);
}

/*---------------------------------------------------------------------------*/

void esc_list_removeItem(esc_list_t* list, void* item)
{
    if ( !item )
        return;
        
    esc_list_location_t location;
    
    if ( private_findListItem(list, item, &location) != -1 ) 
        private_removeListItem(list, &location);
}

/*---------------------------------------------------------------------------*/

void* esc_list_removeIndex(esc_list_t* list, int index)
{
    esc_list_location_t location;
    
    if ( private_findListIndex(list, index, &location, false) ) {
        void* result = location.node->entries[location.entryIndex];
        private_removeListItem(list, &location);
        
        return result;
    }
    else
        return NULL;
}

/*---------------------------------------------------------------------------*/

void esc_list_removeAll(esc_list_t* list)
{
    esc_list_node_t* node = list->head;
    
    while ( node ) {
        int entryCount = node->entryCount;
        void** entries = node->entries;
        
        for ( int i = 0; i < entryCount; i++ ) 
            esc_ptr_release(entries[i]);
            
        esc_list_node_t* next = node->next;
        esc_ptr_free(node);
        node = next;
    }
    
    list->listSize = 0;
    list->head = NULL;
    list->tail = NULL;
}

/*---------------------------------------------------------------------------*/

void* esc_list_getItem(esc_list_t* list, int index)
{
    esc_list_location_t location;
    
    if ( private_findListIndex(list, index, &location, false) )
        return location.node->entries[location.entryIndex];
    else
        return NULL;
}

/*---------------------------------------------------------------------------*/

int esc_list_getIndex(esc_list_t* list, void* item)
{
    esc_list_location_t location;
    
    return private_findListItem(list, item, &location);
}

/*---------------------------------------------------------------------------*/

void* esc_list_setItem(esc_list_t* list, int index, void* item)
{
    if ( !item )
        return NULL;
        
    if ( index >= list->listSize ) {
        esc_list_addItem(list, item);
        
        return NULL;
    }
    else if ( index < 0 ) {
        esc_list_insertItem(list, 0, item);
        
        return NULL;
    }
    else {
        esc_list_location_t location;
        private_findListIndex(list, index, &location, false);
        esc_list_node_t* node = location.node;
        int entryIndex = location.entryIndex;
        void* oldItem = node->entries[entryIndex];
        
        esc_ptr_retain(item);        
        esc_ptr_release(oldItem);
        
        node->entries[entryIndex] = item;
        
        return oldItem;
    }
}

/*---------------------------------------------------------------------------*/

void esc_list_replaceItem(esc_list_t* list, void* oldItem, void* newItem)
{
    if ( !oldItem )
        return;
        
    if ( newItem ) {
        esc_list_location_t location;
        
        if ( private_findListItem(list, oldItem, &location) != -1 ) {            
            esc_ptr_retain(newItem);            
            esc_ptr_release(oldItem);
            
            location.node->entries[location.entryIndex] = newItem;
        }
    }
    else
        esc_list_removeItem(list, oldItem);
}

/*---------------------------------------------------------------------------*/

int esc_list_getSize(esc_list_t* list)
{
    return list->listSize;
}

/*---------------------------------------------------------------------------*/

bool esc_list_isEmpty(esc_list_t* list)
{
    return list->listSize == 0;
}

/*---------------------------------------------------------------------------*/

esc_status_t esc_list_iterate(esc_list_t* list, esc_list_iterator_t* iterator, 
                              void* context)
{
    esc_list_location_t location;
        
    esc_list_node_t* node = list->head;
    
    while ( node ) {
        int entryCount = node->entryCount;
        void** entries = node->entries;
        
        for ( int i = 0; i < entryCount; ) {
            esc_status_t result = iterator(list, entries[i], context);
            
            switch ( result ) {
                case ESC_SUCCESS:
                    i++;
                    break;
             
                case ESC_LIST_REMOVE:
                    location.node = node;
                    location.entryIndex = i;
                    
                    private_removeListItem(list, &location);
                    
                    node = location.node;
                    i = location.entryIndex;
                    break;
                       
                default:
                    return result;
            }
        }
        
        node = node->next;
    }
    
    return ESC_SUCCESS;
}
